package bintree.nowcoder;

import java.util.Scanner;

/**
 * @Author: yuisama
 * @Date: 2021/9/8 13:52
 * @Description:根据二叉树的先序遍历构建二叉树输出其中序遍历结果
 * https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking
 */
public class BuildTree {
    private static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    private static int index = 0;

    public static TreeNode build(String line) {
        // 引入index为了方便记录在递归构造过程中访问到line中的哪个元素了
        return preOrderCreate(line);
    }

    private static TreeNode preOrderCreate(String line) {
        // 获取当前处理到哪个节点了
        char cur = line.charAt(index);
        if (cur == '#') {
            return null;
        }
        // 当前字符只要不是'#'，就需要创建新节点
        TreeNode node = new TreeNode(cur);
        // index++，继续处理后续元素
        index++;
        // 处理左子树
        node.left = preOrderCreate(line);
        index++;
        // 处理右子树
        node.right = preOrderCreate(line);
        return node;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String line = scanner.next();
            // 根据先序遍历构建二叉树
            TreeNode root = build(line);
            // 得到的二叉树输出中序遍历结果
            inOrder(root);
            System.out.println();
        }
    }

    private static void inOrder(TreeNode root) {
        if (root == null)
            return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
}
